package com.ljx.offer;

import org.junit.Test;

import java.util.Collections;
import java.util.LinkedList;

/**
 * todo 前置知识学习一下排序
 * @author 李捷禧
 * Date: 2023/3/16
 * ClassName: C_40
 */

public class C_40 {

    /**
     * 同样使用的是从小到大先排序，输出前k个
     * 排序用到的是Collections.sort(list);
     * 运行时间缩短了，内存变大了
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers1(int[] arr, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i : arr) {
            list.addLast(i);
        }
        // 这等同于作弊了
        Collections.sort(list);
        int[] nums = new int[k];
        for (int i = 0; i < k; i++) {
            nums[i] = list.removeFirst();
        }
        return nums;
    }


    /**
     * 暴力解法
     * 先对数组从小到大排列，然后输出所要求的个数
     * 运行时间比较长
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] nums = new int[k];
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0;j--) {
                int t;
                if(arr[j]<=arr[j-1]){
                    t = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = t;
                }
            }
        }
//        for (int i : arr) {
//            System.out.print(i+" ");
//        }
//        System.out.println();
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
        return nums;
    }

    @Test
    public void test(){
        int[] arr = new int[]{2,5,1,6,6,4};
        for (int leastNumber : getLeastNumbers(arr, 2)) {
            System.out.println(leastNumber);
        }
    }
}
